package com.justnow.offer;

/**
 * @author JustNow
 * @create 2020-04-29 9:13
 */
public class Solution5 {
    public static void main(String[] args) {
        Solution5 solution5 = new Solution5();
        String abad = solution5.longestSubString("abad");
        //System.out.println(abad);
        String test = "123456789";
        System.out.println(test.substring(0, 1));
        System.out.println(test.substring(0, 2));
        System.out.println(test.substring(0, 3));
        System.out.println(test.substring(0, 4));
    }

    /**
     * 判断一个字符串是不是一个回文字符串
     * @param s
     * @return
     */
    public boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i -1)) {
                return false;
            }
        }

        return true;
    }

    /**
     * 方法一，暴力解法
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        }
        return ans;
    }

    /**
     * 方法二，动态规划思想
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        if (s.equals(""))
            return "";
        String origin = s;
        String reverse = new StringBuilder(s).reverse().toString(); //字符串的倒置
        int length = s.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (origin.charAt(i) == reverse.charAt(j)) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i -1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxLen) {
/*
                    maxLen = arr[i][j];
                    maxEnd = i; //以i结尾的字符
*/
                    //修改的地方
                    int beforeRev = length - 1 - j;
                    if (beforeRev + arr[i][j] - 1 == i) {//判断下标是否对应
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);

    }

    public String longestSubString(String s) {
        if (s.equals(""))
            return "";
        String origin = s;
        String reverse = new StringBuilder(s).reverse().toString(); //字符串的倒置
        int length = s.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (origin.charAt(i) == reverse.charAt(j)) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i -1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxLen) {
                    maxLen = arr[i][j];
                    maxEnd = i; //以i结尾的字符
                }
            }
        }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
    }

    /**
     * 方法三，另一种动态规划
     */
    public String longestPalindrome3(String s) {
        int len = s.length();
        //特判
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;

        //1. 状态定义
        //dp[i][j] 表示s[i...j]是否是回文串

        //2. 初始化
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] chars = s.toCharArray();

        //3. 状态转移
        //注意：当前位置的是否为true由,左下角元素来决定
        //填表规则：先按照列递增,然后按照行递增的顺序.如我们在第1列,那么先填写第一列的第一行，然后是第二行直到对角线；接着是第二列的第一行，然后按照行递增。
        for (int j = 0; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    //相等的情况下
                    //考虑头尾去掉以后没有字符剩余,或者剩下一个字符的时候,肯定是回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        //状态转移
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        //4. 返回值
        return s.substring(begin, begin + maxLen);
    }

    /**
     * 方法四 中心扩散法
     * https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
     * @param s
     * @return
     */
    public String longestPalindrome4(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        //初始化最大回文字符串的起点和终点
        return "";
    }
}
